Week 3 Deep Internal Analysis: Recurrences & Struct Padding
Section 1: Mathematical Proof of Merge Sort Asymptotics
To definitively substantiate how Merge Sort achieves an asymptotic runtime leap down to O(n log n), we deconstruct its formal recurrence relation via the Recursion Tree Method.
===================================================================================
MERGE SORT RECURSION TREE DECONSTRUCTION
===================================================================================
Level 0: [ n ] ──> Work: O(n)
/ \
Level 1: [ n/2 ] [ n/2 ] ──> Work: 2 * (n/2) = O(n)
/ \ / \
Level 2: [ n/4 ] [ n/4 ] [ n/4 ] [ n/4 ] ──> Work: 4 * (n/4) = O(n)
Total Depth = log_2(n) ──> Total Execution Cost: O(n * log n)
===================================================================================
- Mathematical Deconstruction: Bisecting the array requires constant time O(1). Self-invoking yields 2T(n/2). The merge operation demands linear inspection O(n).
Section 2: Memory Alignment & Struct Padding
CPUs fetch memory blocks along 4-byte or 8-byte word boundaries. If a struct contains a char followed by an int, the bare-metal compiler automatically injects unused padding bytes to preserve word alignment.
===================================================================================
PHYSICAL STRUCT MEMORY PADDING (64-BIT ARCH)
===================================================================================
struct { char c; int i; };
[ 0x100: char c (1B) ] [ 0x101-0x103: PADDING (3B) ] [ 0x104-0x107: int i (4B) ]
Total Size in RAM = 8 Bytes (not 5 Bytes!)
===================================================================================
- The Padding Phenomenon: Expanding physical memory allocation to optimize processor bus alignment speeds.
Section 3: Activation Record Dynamics during Deep Recursion
Every discrete invocation of a recursive subroutine forces the runtime kernel to push an activation record containing return addresses, arguments, and local variables.
- MMU Hardware Traps: If the cumulative recursive call depth breaches the allocated stack bound, the MMU intercepts the trap and dispatches a fatal SIGSEGV segmentation fault.